CS154 Spring 2003Practice Midterm 1

The practice midterm is below. Here are some facts about the actual midterm: (a) The midterm will be in class . (b) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (c) You should bring photo ID. (d) There will be more than one version of the test. Each version will be of comparable difficulty. (e) If your cell-phone or beeper goes off you will be excused from the test at that point and graded on what you have done till your excusal. (f) One problem (less typos) on the actual test will be from the practice test.

1. Show the set of all regular languages over the alphabet {0, 1} is countable.

2. Give the reflexive, transitive closure of the set

{(a,b), (c,d), (e,f), (d,e), (b,b)}

3. Using a construction involving the cartesian product of the states of of two finite automata M1, M2, show that L(M1)-L(M2) is regular.

4. Using the algorithm from class construct an NFA for the language L(a(ab)^*b).

5. Using the algorithm from class convert the NFA of problem (4) to an equivalent DFA.

6. Consider the following DFA:

M=({1,2},{a,b}, {(1,a)->2, (1,b)->1, (2,a)->2, (2,b)->2 }, 1, {1})

Use the algorithm from class to determine a regular expression for L(M).

7. Show the language L={a³ⁿ : n ³0} is not regular.

8. Using the algorithm from class compute the equivalences classes º₀ and º₁ for the machine from Problem 6.

9. Given that L and L' are regular show that the quotient language L/L' = { w : wx Î L where x Î L' } is regular.

10. Give a context free grammar for the language: L = {baⁿb²ⁿa : n ³0}.